/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-08-08
 * Time: 22:45
 */

import java.util.*;

/**
 * 奇偶链表
 * 定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
 *
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
 *
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 *
 * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/odd-even-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
public class Demo01 {

    public ListNode oddEvenList(ListNode head) {
        if( head == null || head.next == null) return head;
        ListNode cur = head;
        ListNode prev = null;
        ListNode prev1 = head.next;
        int len = 0;
        while( cur!=null && cur.next!=null ) {
            len++;
            ListNode tmp = cur.next;
            prev = cur;
            cur.next = cur.next.next;
            cur = tmp;
        }
        if( (len+1) % 2 != 0) {
            cur.next = prev1;
        } else {
            prev.next = prev1;
        }
        return head;
    }
    /**
     用栈操作构建数组
     给你一个目标数组 target 和一个整数 n。每次迭代，需要从  list = {1,2,3..., n} 中依序读取一个数字。

     请使用下述操作来构建目标数组 target ：

     Push：从 list 中读取一个新元素， 并将其推入数组中。
     Pop：删除数组中的最后一个元素。
     如果目标数组构建完成，就停止读取更多元素。
     题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

     请返回构建目标数组所用的操作序列。

     题目数据保证答案是唯一的。
     示例 1：
     输入：target = [1,3], n = 3
     输出：["Push","Push","Pop","Push"]
     解释：
     读取 1 并自动推入数组 -> [1]
     读取 2 并自动推入数组，然后删除它 -> [1]
     读取 3 并自动推入数组 -> [1,3]


     */
    public List<String> buildArray(int[] target, int n) {
        /*方法一 ( 使用辅助栈)
        List<String> ret = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int num;
        int i;
        for(  num = 1, i = 0 ; num <=n && i< target.length ; num++) {
             ret.add("Push");
             stack.push(num);
             if( target[i] != stack.pop()) {
                 ret.add("Pop");
             } else {
                 i++;
             }
        }
        return ret;*/
        //方法二 同时遍历target 和 list , 相同就加入push , 不同就加入 push 和 pop
        List<String> ret = new ArrayList<>();
        for( int num = 1, index=0;  num<= n && index < target.length; num++) {
            if( num == target[index]) {
                ret.add("Push");
                index++;
            } else {
                ret.add( "Push");
                ret.add( "Pop");
            }
        }
        return ret;
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        /**
         解法一 : 暴力破解
         int [] ans = new int[nums1.length];
         int k = 0;
         for( int i=0; i<nums1.length; i++) {
         for( int j=0; j<nums2.length; j++) {
         if( nums1[i] == nums2[j] ) {
         if( j == nums2.length -1) {
         ans[k++] = -1;
         break;
         }
         int m = j+1;
         while( m<nums2.length) {
         if( nums2[m] <= nums2[j]) {
         m++;
         } else {
         ans[k++] = nums2[m];
         break;
         }
         }
         if( m>=nums2.length){
         ans[k++] = -1;
         }
         }
         }
         }
         return ans;
         */
        //解法二 :借助辅助栈, 正序遍历nums2
        Stack<Integer> stack = new Stack<>();
        Map<Integer,Integer> map = new HashMap<>();
        stack.push(nums2[0]);
        for( int i=1;i<nums2.length;i++) {
            if(  !stack.isEmpty() && nums2[i] > stack.peek()) {
                map.put( stack.peek() , nums2[i]);
            } else {
                stack.pop();
            }
        }
        int [] ans = new int[ nums1.length];
        int k=0;
        for( int i=0; i<nums1.length; i++) {
            ans[k++] = map.getOrDefault()
        return ans;
    }
/**
 *   最小栈
 *   设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 *
 * 实现 MinStack 类:
 *
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 *   //解法一 :使用两个辅助栈
 */
        class MinStack {
            Stack<Integer> minstack;
            Stack<Integer> datastack;
            public MinStack() {
                minstack = new Stack<>();
                datastack = new Stack<>();
            }

            public void push(int val) {
                datastack.push(val);
                if( minstack.isEmpty() || val <= minstack.peek() ) {
                    minstack.push(val);
                }
            }

            public void pop() {
                int x = datastack.pop();
                if( minstack.peek() == x) {
                    minstack.pop();
                }
            }

            public int top() {
                return datastack.peek();
            }

            public int getMin() {
                return minstack.peek();
            }
        }

        //

        class MinStack2 {
            Stack<Node> stack;
            int min;
            public MinStack2() {
                stack = new Stack<>();
            }

            public void push(int val) {
                if( stack.isEmpty()) {
                    stack.push(new Node( val,val));
                } else {
                    if( val <=min) {
                        min = val;
                    }
                    stack.push(new Node(val,min));
                }

            }

            public void pop() {
                stack.pop();
            }

            public int top() {
                return stack.peek().v;
            }

            public int getMin() {
                return stack.peek().m;
            }

            class Node{
                int v;
                int m;
                public Node(int val,int min){
                    this.v = val;
                    this.m = min;
                }
            }
        }

    }
